package interview.array;

import java.util.*;

/**
 * 找出三数只和为0的 数组
 * 要求：三元组不可重复，但是数字可以重复使用
 *
 * 思路：双指针法
 *
 * Created by yzy on 2021-02-06 14:44
 */
public class ThreeSum {
    public static void main(String[] args) {
        int[] arr = new int[]{-2,0,0,2,2};
        List<List<Integer>> lists = threeSum(arr);
        System.out.println(lists);
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);  // 先排序方便去重
        List<List<Integer>> resList = new ArrayList<>();
        for(int i=0; i<nums.length; i++){
            if(nums[i] > 0){
                break;
            }
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }

            int leftIdx = i+1;
            int rightIdx = nums.length-1;
            while(leftIdx < rightIdx){
                int tmp = nums[i] + nums[leftIdx] + nums[rightIdx];
                if(tmp == 0){
                    List<Integer> list = Arrays.asList(nums[i], nums[leftIdx], nums[rightIdx]);
                    resList.add(list);
                    // 注意：这里 while循环, 往后跳过一模一样的元素
                    while(leftIdx < rightIdx && nums[leftIdx] == list.get(1)) leftIdx++;
                    while(leftIdx < rightIdx && nums[rightIdx] == list.get(2)) rightIdx--;
                }else if(tmp < 0){
                    leftIdx++;
                }else{
                    rightIdx--;
                }
            }

        }
        return resList;
    }
}
